#include "headfiles.h"

using namespace std;

static int findRootIndex(int *array, int n, int val) {
    int i;
    for (i = 0; i < n; i++) {
        if (array[i] == val) {
            return i;
        }
    }

    return -1;
}

TNODE *preOrderInOrderBinaryTree(int *pre_order, int *in_order, int n) {
    if (pre_order == NULL ||
        in_order == NULL ||
        n <= 0) {
        return NULL;
    }

    TNODE *root = new TNODE;
    memset(root, 0, sizeof(TNODE));

    // First element in the pre_order list is the root node
    root->val = pre_order[0];
    if (n == 1) {
        return root;
    }
    
    // Find the root in the in_order list, then the left part
    // belongs to the left subtree and the right part belongs
    // to the right subtree.
    int root_index = findRootIndex(in_order, n, root->val);
    if (root_index == -1) {
        cout << "Incorrect input for in_order list!" << endl;
        delete root;
        return NULL;
    }

    // Construct the left and right subtree
    root->left = preOrderInOrderBinaryTree(&pre_order[1], &in_order[0], root_index);
    root->left ->parent = root;
    root->right = preOrderInOrderBinaryTree(&pre_order[root_index + 1], &in_order[root_index + 1], n - root_index - 1);
    root->right ->parent = root;

    return root;
}

